class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> v;
        TreeNode* cur = root;
        TreeNode* prve = nullptr;
        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);
                cur = cur->left;
            }

            TreeNode* top = s.top();
            if (top->right == nullptr || top->right == prve)
            {
                s.pop();
                v.push_back(top->val);
                prve = top;
            }
            else
            {
                cur = top->right;
            }
        }
        return v;
    }
};
class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& pi, int inbeing, int inend) {
        if (inbeing > inend)
            return nullptr;
        TreeNode* root = new TreeNode(preorder[pi++]);
        int rooti = inbeing;
        while (rooti <= inend)
        {
            if (root->val == inorder[rooti])
                break;
            else
                rooti++;
        }

        root->left = _buildTree(preorder, inorder, pi, inbeing, rooti - 1);
        root->right = _buildTree(preorder, inorder, pi, rooti + 1, inend);

        return root;

    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    }
};